Packet-switched networks route data from a source to a destination in packets. A packet is a relatively small sequence of digital symbols (e.g., several tens of binary octets up to several thousands of binary octets) that contains a payload and one or more headers. The payload is the information which the source wishes to send to the destination. The headers contain information about the nature of the payload and its delivery. For instance, headers can contain a source address, a destination address, data length and data format information, data sequencing or timing information, flow control information, and error correction information.
A packet's payload can consist of just about anything that can be conveyed as digital information. Some examples are e-mail, computer text, graphic, and program files, web browser commands and pages, and communication control and signaling packets. Other examples are streaming audio and video packets, including real-time bidirectional audio and/or video conferencing. In Internet Protocol (IP) networks, a two-way (or multipoint) audio conference that uses packet delivery of audio is usually referred to as Voice over IP, or VoIP.
The urgency with which a given packet should be delivered depends to a great extent on the type of payload. E-mail and background file transfers are among the least urgent, as delays of minutes can usually easily be tolerated. On the other end of the spectrum, VoIP packets typically must be delivered within a few hundred milliseconds of their creation, or VoIP call quality begins to degrade noticeably. Other relatively high-priority packets can include data link flow control packets and network node status packets.
Since high-priority packets and low-priority packets must share the packet network, various schemes have been proposed to provide fair allocation of network resources between the two. For instance, FIG. 1 illustrates a portion of a device 20, e.g., implemented on a computer, that multiplexes VoIP packets and other data packets onto a common data link using a priority queuing mechanism. The VoIP packets are created by digitally encoding a voice capture channel (e.g., from a microphone or headset) using an A/D (analog-to-digital) converter 22 and a voice encoder 26. Data packets are received from other applications running on the computer, e.g., a web-browser, e-mail application, or networked file system application.
Device 20 uses two packet queues. A time-critical-packet queue 28 queues VoIP packets as they are created. A data packet queue 36 queues lower-priority packets. Note that in FIG. 1, data packets pass through an optional data packet fragmenter 34, which segments large data packets into sequences of smaller data packets before submission to queue 36. Note also that signal packets from controller 24 are submitted to data packet queue 36. The signal packets provide overall coordination of VoIP call setup and termination, among other things, and may optionally be placed in queue 28.
Packet scheduler 30 multiplexes packets from queues 28 and 36 to data link interface 32. Under one prior art method of operation, scheduler 30 selects time-critical packets from queue 28 until queue 28 is emptied. When queue 28 is empty, scheduler 30 then selects packets from data packet queue 36. When queue 28 receives one or more additional time-critical packets, scheduler 30 switches back to queue 28 until that queue is once again empty.
The priority operation of scheduler 30 can be better understood with reference to the timing diagrams of FIGS. 2, 3, and 4. Referring first to FIG. 2, a single talkspurt on the voice capture channel is represented. The overall duration of the talkspurt is tTS1.
Voice encoder 26 groups voice samples from A/D converter 22 into voice sample blocks 1-1, 1-2, . . . , 1-8. Each sample block represents the same fixed number of voice samples, e.g., 80 samples, 240 samples, etc. Because the number of samples is fixed, block 1-8 extends past the end of the talkspurt in order to take in the appropriate number of samples.
Voice encoder 26 encodes each sample block into a voice packet. Simple encoders may do no more than place the entire sample block in a packet payload and attach addressing headers. More sophisticated encoders may compress the sample block using a variety of known coding techniques. In either case, the encoder cannot place a voice packet in packet queue 28 until sometime after the entire sample block is received at encoder 26—if sophisticated coding must also take place, additional delay may occur while the data is compressed. FIG. 2 illustrates the packet formation delay, tPF, as the time between when the first sample of a sample block is generated and when the packet corresponding to that sample block is queued.
When the time-critical packets do not have to compete for data link bandwidth (and the bandwidth of the channel is large compared to packet size), total packet transmission delay is not much greater than packet formation delay. Packet transmission delay, tTX, is the time between when the first sample of a sample block is generated and when transmission of the packet corresponding to that sample block has completed.
It is believed to have been heretofore unrecognized that time-critical packet transmission can be negatively affected, even with priority queuing. FIG. 3 shows packet transmission delay when two data packets are placed in data queue 28 shortly after voice packet VP1.1 is placed in queue 26. Once VP1.1 has been placed on the data link, queue 26 is empty. Scheduler 30 thus checks queue 36, finds data packet DP1 waiting, and selects that data packet for transmission. While the data packet is transmitting, voice packets VP1.2, VP1.3, and VP1.4 arrive at queue 26. Thus, a four-packet delayed “burst” of voice packets occurs at the end of data packet DP1 transmission. With queue 26 once again empty, data packet DP2 from queue 36 is selected for transmission, causing another four-packet burst of voice packets to occur. In addition to the voice sample “bursting” phenomenon, data packet transmission has caused the transmission delay tTX for voice sample block 1-2, for example, to be substantially longer than the comparable delay in FIG. 2.
FIG. 4 shows the same scenario as FIG. 3, but using data packet fragmenter 34 to segment the two data packets of FIG. 3 into eight smaller data packets. Although this tends to improve the regularity of voice packet transmission and lessen the average voice packet transmission delay, the problem is not completely cured.